package Q384;

import java.util.*;

/**
 * 打乱数组
 * 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
 * <p>
 * 实现 Solution class:
 * <p>
 * Solution(int[] nums) 使用整数数组 nums 初始化对象
 * int[] reset() 重设数组到它的初始状态并返回
 * int[] shuffle() 返回数组随机打乱后的结果
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shuffle-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author 23737
 * @time 2021.11.22
 */
public class Test {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        Solution obj = new Solution(nums);
        int[] param_1 = obj.reset();
        int[] param_2 = obj.shuffle();
        for (int i : param_1) {
            System.out.print(i);
        }
        System.out.println();
        System.out.println("------------------");
        for (int i : param_2) {
            System.out.print(i);
        }

        System.out.println();
        System.out.println("两种算法的分割线");

        Solution obj2 = new Solution(nums);
        int[] param_3 = obj2.reset();
        int[] param_4 = obj2.shuffle();
        for (int i : param_3) {
            System.out.print(i);
        }
        System.out.println();
        System.out.println("------------------");
        for (int i : param_4) {
            System.out.print(i);
        }
    }
}

/**
 * 我自己的解法（超时了）：
 * 重置功能很好写，直接用一个新数组将原来的数组传进来就好了；
 * 扰乱功能我个人想法是利用全排列生成一个集合，然后再生成一个在0-集合长度的随机数来取得数组然后返回、
 * 个人测试是没有问题的，全排列的算法是用回溯写的。
 * 超时的愿原因可能就是全排列那里。
 */
class Solution {

    public static int[] array = null;
    public int[] result = null;
    private Random random;

    public Solution(int[] nums) {
        //将原有的数组存储到一个新数组中
        array = Arrays.copyOf(nums, nums.length);

        //初始化结果数组
        result = new int[nums.length];
    }

    public int[] reset() {
        return Arrays.copyOf(array, array.length);
    }

    public int[] shuffle() {
        result = Arrays.copyOf(array, array.length);
        List<List<Integer>> permute = permute(result);
        //生成一个随机数
        random = new Random();

        int min = 0;
        int max = permute.size();
        int randomNumber = random.nextInt(max) % (max - min + 1) + min;

        //从重排列中抽出来一个数组
        List<Integer> list = permute.get(randomNumber);
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        if (nums.length == 0) {
            return list;
        }
        int length = nums.length;
        Deque<Integer> path = new ArrayDeque<>();
        boolean[] used = new boolean[length];
        dfs(nums, length, 0, path, used, list);
        return list;
    }

    private void dfs(int[] nums, int length, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> list) {
        if (depth == length) {
            list.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < length; i++) {
            //防止重复
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            path.addLast(nums[i]);
            used[i] = true;
            dfs(nums, length, depth + 1, path, used, list);
            path.removeLast();
            used[i] = false;
        }
    }
}

/**
 * 使用洗牌算法来解题
 */
class Solution2 {

    public static int[] array = null;
    public int[] result = null;
    private Random random;

    private void swap(int i, int j) {
        int temp = result[i];
        result[i] = result[j];
        result[j] = temp;
    }

    public Solution2(int[] nums) {
        //将原有的数组存储到一个新数组中
        array = Arrays.copyOf(nums, nums.length);

        //初始化结果数组
        result = new int[nums.length];

        //初始化Random
        random = new Random();
    }

    public int[] reset() {
        return Arrays.copyOf(array, array.length);
    }

    //Jdk  Collections.shuffle()方法
    public int[] shuffle() {
        result = Arrays.copyOf(array, array.length);
        for (int i = result.length; i > 1; i--) {
            swap(i - 1, random.nextInt(i));
        }
        return result;
    }
}
